home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Python 1.4 / Python 1.4 source / Extensions / img / mppm3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-03-18  |  6.0 KB  |  260 lines  |  [TEXT/CWIE]
  1. /*
  2. ** mppm3.c - Handle color histograms and hash tables.
  3. **
  4. ** Modified from: libppm3.c - ppm utility library part 3
  5. **
  6. ** Colormap routines.
  7. **
  8. ** Copyright (C) 1989, 1991 by Jef Poskanzer.
  9. **
  10. ** Permission to use, copy, modify, and distribute this software and its
  11. ** documentation for any purpose and without fee is hereby granted, provided
  12. ** that the above copyright notice appear in all copies and that both that
  13. ** copyright notice and this permission notice appear in supporting
  14. ** documentation.  This software is provided "as is" without express or
  15. ** implied warranty.
  16. */
  17.  
  18. #include "Python.h"
  19. #include "mppmcmap.h"
  20.  
  21. #define HASH_SIZE 20023
  22.  
  23. #define mppm_hashpixel(p) ( ( (int) (p) & 0xffffff ) % HASH_SIZE )
  24.  
  25. colorhist_vector
  26. mppm_computecolorhist( pixels, cols, rows, maxcolors, colorsP )
  27.     pixel* pixels;
  28.     int cols, rows, maxcolors;
  29.     int* colorsP;
  30.     {
  31.     colorhash_table cht;
  32.     colorhist_vector chv;
  33.  
  34.     cht = mppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP );
  35.     if ( cht == (colorhash_table) 0 )
  36.     return (colorhist_vector) 0;
  37.     chv = mppm_colorhashtocolorhist( cht, maxcolors );
  38.     mppm_freecolorhash( cht );
  39.     return chv;
  40.     }
  41.  
  42. void
  43. mppm_addtocolorhist( chv, colorsP, maxcolors, colorP, value, position )
  44.     colorhist_vector chv;
  45.     pixel* colorP;
  46.     int* colorsP;
  47.     int maxcolors, value, position;
  48.     {
  49.     int i, j;
  50.  
  51.     /* Search colorhist for the color. */
  52.     for ( i = 0; i < *colorsP; ++i )
  53.     if ( MPPM_EQUAL( chv[i].color, *colorP ) )
  54.         {
  55.         /* Found it - move to new slot. */
  56.         if ( position > i )
  57.         {
  58.         for ( j = i; j < position; ++j )
  59.             chv[j] = chv[j + 1];
  60.         }
  61.         else if ( position < i )
  62.         {
  63.         for ( j = i; j > position; --j )
  64.             chv[j] = chv[j - 1];
  65.         }
  66.         chv[position].color = *colorP;
  67.         chv[position].value = value;
  68.         return;
  69.         }
  70.     if ( *colorsP < maxcolors )
  71.     {
  72.     /* Didn't find it, but there's room to add it; so do so. */
  73.     for ( i = *colorsP; i > position; --i )
  74.         chv[i] = chv[i - 1];
  75.     chv[position].color = *colorP;
  76.     chv[position].value = value;
  77.     ++(*colorsP);
  78.     }
  79.     }
  80.  
  81. colorhash_table
  82. mppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP )
  83.     pixel* pixels;
  84.     int cols, rows, maxcolors;
  85.     int* colorsP;
  86.     {
  87.     colorhash_table cht;
  88.     register pixel* pP;
  89.     colorhist_list chl;
  90.     int col, hash;
  91.  
  92.     cht = mppm_alloccolorhash( );
  93.     *colorsP = 0;
  94.  
  95.     /* Go through the entire image, building a hash table of colors. */
  96.     for ( col = 0, pP = pixels; col < cols*rows; ++col, ++pP )
  97.     {
  98.     hash = mppm_hashpixel( *pP );
  99.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  100.         if ( MPPM_EQUAL( chl->ch.color, *pP ) )
  101.         break;
  102.     if ( chl != (colorhist_list) 0 )
  103.         ++(chl->ch.value);
  104.     else
  105.     {
  106.         if ( ++(*colorsP) > maxcolors )
  107.         {
  108.         mppm_freecolorhash( cht );
  109.         return (colorhash_table) 0;
  110.         }
  111.         chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  112.         if ( chl == 0 )
  113.         pm_error( "out of memory computing hash table" );
  114.         chl->ch.color = *pP;
  115.         chl->ch.value = 1;
  116.         chl->next = cht[hash];
  117.         cht[hash] = chl;
  118.     }
  119.     }
  120.     
  121.     return cht;
  122.     }
  123.  
  124. colorhash_table
  125. mppm_alloccolorhash( )
  126.     {
  127.     colorhash_table cht;
  128.     int i;
  129.  
  130.     cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) );
  131.     if ( cht == 0 )
  132.     pm_error( "out of memory allocating hash table" );
  133.  
  134.     for ( i = 0; i < HASH_SIZE; ++i )
  135.     cht[i] = (colorhist_list) 0;
  136.  
  137.     return cht;
  138.     }
  139.  
  140. int
  141. mppm_addtocolorhash( cht, colorP, value )
  142.     colorhash_table cht;
  143.     pixel* colorP;
  144.     int value;
  145.     {
  146.     register int hash;
  147.     register colorhist_list chl;
  148.  
  149.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  150.     if ( chl == 0 )
  151.     return -1;
  152.     hash = mppm_hashpixel( *colorP );
  153.     chl->ch.color = *colorP;
  154.     chl->ch.value = value;
  155.     chl->next = cht[hash];
  156.     cht[hash] = chl;
  157.     return 0;
  158.     }
  159.  
  160. colorhist_vector
  161. mppm_colorhashtocolorhist( cht, maxcolors )
  162.     colorhash_table cht;
  163.     int maxcolors;
  164.     {
  165.     colorhist_vector chv;
  166.     colorhist_list chl;
  167.     int i, j;
  168.  
  169.     /* Now collate the hash table into a simple colorhist array. */
  170.     chv = (colorhist_vector) malloc( maxcolors * sizeof(struct colorhist_item) );
  171.     /* (Leave room for expansion by caller.) */
  172.     if ( chv == (colorhist_vector) 0 )
  173.     pm_error( "out of memory generating histogram" );
  174.  
  175.     /* Loop through the hash table. */
  176.     j = 0;
  177.     for ( i = 0; i < HASH_SIZE; ++i )
  178.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next )
  179.         {
  180.         /* Add the new entry. */
  181.         chv[j] = chl->ch;
  182.         ++j;
  183.         }
  184.  
  185.     /* All done. */
  186.     return chv;
  187.     }
  188.  
  189. colorhash_table
  190. mppm_colorhisttocolorhash( chv, colors )
  191.     colorhist_vector chv;
  192.     int colors;
  193.     {
  194.     colorhash_table cht;
  195.     int i, hash;
  196.     pixel color;
  197.     colorhist_list chl;
  198.  
  199.     cht = mppm_alloccolorhash( );
  200.  
  201.     for ( i = 0; i < colors; ++i )
  202.     {
  203.     color = chv[i].color;
  204.     hash = mppm_hashpixel( color );
  205.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  206.         if ( MPPM_EQUAL( chl->ch.color, color ) )
  207.         pm_error(
  208.             "same color found twice - %d %d %d", MPPM_GETR(color),
  209.             MPPM_GETG(color), MPPM_GETB(color) );
  210.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  211.     if ( chl == (colorhist_list) 0 )
  212.         pm_error( "out of memory" );
  213.     chl->ch.color = color;
  214.     chl->ch.value = i;
  215.     chl->next = cht[hash];
  216.     cht[hash] = chl;
  217.     }
  218.  
  219.     return cht;
  220.     }
  221.  
  222. int
  223. mppm_lookupcolor( cht, colorP )
  224.     colorhash_table cht;
  225.     pixel* colorP;
  226.     {
  227.     int hash;
  228.     colorhist_list chl;
  229.  
  230.     hash = mppm_hashpixel( *colorP );
  231.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  232.     if ( MPPM_EQUAL( chl->ch.color, *colorP ) )
  233.         return chl->ch.value;
  234.  
  235.     return -1;
  236.     }
  237.  
  238. void
  239. mppm_freecolorhist( chv )
  240.     colorhist_vector chv;
  241.     {
  242.     free( (char*) chv );
  243.     }
  244.  
  245. void
  246. mppm_freecolorhash( cht )
  247.     colorhash_table cht;
  248.     {
  249.     int i;
  250.     colorhist_list chl, chlnext;
  251.  
  252.     for ( i = 0; i < HASH_SIZE; ++i )
  253.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext )
  254.         {
  255.         chlnext = chl->next;
  256.         free( (char*) chl );
  257.         }
  258.     free( (char*) cht );
  259.     }
  260.